package alogrithm;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/10/26 16:03
 * LeetCode第496题, 下一个更大的元素
 */
public class NextGreaterElement {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        int n = nums2.length;
        for (int i = n - 1; i >= 0; --i) {
            int num = nums2[i];
            while (!stack.isEmpty() && num > stack.peek()) {
                stack.push(num);
            }
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        int len = nums1.length;
        int[] res = new int[len];
        for (int i = 0; i < len; ++i) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}
